#include "scheduler.h"
#include <stdio.h>

// int append_stage(struct stage* parent_stage, struct stage* child_stage){
//     child_stage->next_paralle_stage = parent_stage->next_stage_head; //不需要判断是否为NULL
//     parent_stage->next_stage_head = child_stage;

//     return 0;
// }

int append_task(struct scheduler* scheduler, struct task* task){
    if(scheduler->task_head==NULL){
        scheduler->task_head=task;
        scheduler->task_tail=task;
    }
    else{
        scheduler->task_tail->next_task = task;
        scheduler->task_tail = task;
    }
}

//这个函数只负责操作链表
void link_stage_to_task(struct task* task, struct stage* stage){
    if(task->stage_queue_head == NULL){ //头为空，那么tail肯定也会空
        task->stage_queue_head = stage;
        task->stage_queue_tail = stage;
    }
    else{
        task->stage_queue_tail->next_stage_of_task = stage;
        task->stage_queue_tail = stage;
    }
}

void add_stage_dependency(struct stage* stage, struct stage* dep_stage, int relationship){
    struct stage_dep* tmp_stage_dep = (struct stage_dep*)malloc(sizeof(struct stage_dep));
    tmp_stage_dep->id = dep_stage->id;
    tmp_stage_dep->status = 0;
    tmp_stage_dep->next = NULL;
    tmp_stage_dep->stage = dep_stage;
    
    if(relationship == PARENT){
        if(stage->parent_stage_head == NULL){
            stage->parent_stage_head = tmp_stage_dep;
        }
        else{
            tmp_stage_dep->next = stage->parent_stage_head;
            stage->parent_stage_head = tmp_stage_dep;
        }
        stage->total_parent_stage++; //将这个任务的父任务++
    }
    else{
        if(stage->child_stage_head == NULL){
            stage->child_stage_head = tmp_stage_dep;
        }
        else{
            tmp_stage_dep->next = stage->child_stage_head;
            stage->child_stage_head = tmp_stage_dep;
        }
    }
}

void remove_from_list(struct stage* stage, struct stage** list_head){ //传入双指针的目的是可能需要改变list_head的值
    if(stage->next_stage_of_status == NULL){ //没后
        if(stage->prev_stage_of_status == NULL){ //没前没后，说明就这一个节点
            (*list_head) = NULL;
        }
        else{ //有前没后,说明是最后一个节点
            stage->prev_stage_of_status->next_stage_of_status = NULL;
        }
    }
    else{ //有后
        if(stage->prev_stage_of_status == NULL){ //有后没前，说明是第一个节点
            (*list_head) = stage->next_stage_of_status;
            stage->next_stage_of_status->prev_stage_of_status = NULL;
        }
        else{ //有前有后，夹在中间
            stage->prev_stage_of_status->next_stage_of_status = stage->next_stage_of_status;
            stage->next_stage_of_status->prev_stage_of_status = stage->prev_stage_of_status;
        }
    }

    //移除了，把stage的指针都清空一下
    stage->next_stage_of_status = NULL;
    stage->prev_stage_of_status = NULL;
}

void insert_to_list(struct stage* stage, struct stage** list_head){
    //插在链表头即可
    if(*list_head != NULL){
        (*list_head)->prev_stage_of_status = stage;
    }

    stage->next_stage_of_status = *list_head; //不需要判断是否为空，是NULL的话直接赋值也可以
    (*list_head) = stage;
}

void print_task_status(struct task* task){
    printf("task %d ready stage: ", task->task_id);
    struct stage* stage_iter = task->ready_stage_head;
    while(stage_iter!=NULL){
        printf("%d ",stage_iter->id);
        stage_iter = stage_iter->next_stage_of_status;
    }
    printf("running stage: ");
    stage_iter = task->running_stage_head;
    while(stage_iter!=NULL){
        printf("%d ",stage_iter->id);
        stage_iter = stage_iter->next_stage_of_status;
    }
    printf("\n");
}

//计算CPD
int get_CPD_of_stage(struct stage* stage){ //获取某一stage的CPD，会递归地算出所有子stage的CPD
    if(stage->CPD != -1)
        return stage->CPD;

    int CPD = 0;
    struct stage_dep* iter = stage->child_stage_head;
    while(iter!=NULL){
        CPD = iter->stage->predict_time + get_CPD_of_stage(iter->stage);
        if(stage->CPD < CPD)
            stage->CPD = CPD;
        iter = iter->next;
    }

    if(stage->CPD == -1) //如果没有子请求，那么赋值为0
        stage->CPD = 0;

    return stage->CPD;
}

void get_CPD_of_task(struct task* task){ //计算所有task中ready list中的stage的CPD
    struct stage* iter = task->ready_stage_head;
    while(iter!=NULL){
        get_CPD_of_stage(iter);
    }
}

//按照CPD的大小顺序插入到相应位置
void push_stage(struct stage* stage, struct stage** list_head){
    stage->next_stage_of_unit = NULL;
    if(*list_head == NULL){
        *list_head = stage;
    }
    else{
        struct stage* iter = *list_head;
        struct stage* pre = NULL;
        while(iter != NULL){
            if(iter == stage){ //如果插入了2个相同的stage(不知道为什么会出现这种情况)
                return;
            }
            if(get_CPD_of_stage(stage) > get_CPD_of_stage(iter)){
                if(pre == NULL){ //说明一来就遇到比他小的了，插在队列头部
                    stage->next_stage_of_unit = *list_head;
                    *list_head = stage;
                }
                else{
                    stage->next_stage_of_unit = iter;
                    pre->next_stage_of_unit = stage;
                }
                return;
            }
            else{ //等于的话仍然往后移，让先来的先执行
                pre = iter;
                iter = iter->next_stage_of_unit;
            }
        }
        pre->next_stage_of_unit = stage; //如果找到末尾都还没有，则插在最后
    }
}

int dispatch_CPCU(struct scheduler* scheduler){
    struct task* task_iter = scheduler->task_head;
    
    while(task_iter != NULL){
        //步骤1.检查running状态的任务，将完成了的任务从running list取出来并设置该任务的状态。然后检查子任务，将完成了所有父任务的请求插入到相应单元的请求队列和ready list中
        struct stage* stage_iter = task_iter->running_stage_head;
        struct stage* next_iter = NULL;
        unsigned long current_time = scheduler->ssd->current_time;
        while(stage_iter!=NULL){
            next_iter = stage_iter->next_stage_of_status; //因为可能会从其所在状态链表中remove，所以要提前把后一个节点保存下来
            //或者sub_request已完成(这部分由process()函数处理不好修改，我们去查询其是否完成即可)
            if(stage_iter->sub_request != NULL){ //与某个io子请求绑定了的，说明是个io请求
                if((stage_iter->sub_request->current_state == SR_COMPLETE)||((stage_iter->sub_request->next_state==SR_COMPLETE)&&(stage_iter->sub_request->next_state_predict_time<=current_time))){
                    //printf("remove stage %d of task %d from running list\n",stage_iter->id, stage_iter->task->task_id);
                    stage_iter->status = FINISH;
                    remove_from_list(stage_iter, &(stage_iter->task->running_stage_head));
                    if(current_time > stage_iter->task->finish_time) //设置这个task的最晚完成的stage的时间，用于输出信息
                        stage_iter->task->finish_time = current_time;   

                    stage_iter->task->total_finished_stage++;
                    //遍历所有子任务，增加其完成的父任务
                    struct stage_dep* child_stage_iter = stage_iter->child_stage_head;
                    while(child_stage_iter!=NULL){
                        child_stage_iter->stage->finished_parent_stage++;
                        if(child_stage_iter->stage->finished_parent_stage >= child_stage_iter->stage->total_parent_stage){ //如果所有父stage都完成了
                            if(child_stage_iter->stage->dispatched == 0){
                                insert_to_list(child_stage_iter->stage, &(child_stage_iter->stage->task->ready_stage_head));
                                child_stage_iter->stage->status = READY;
                                child_stage_iter->stage->dispatched = 1;
                            }
                        }
                        child_stage_iter = child_stage_iter->next;
                    }
                }
            }
            //如果系统时间超过了stage完成时间(用于判断ndp步骤是否完成，因为ndp步骤没有对应的sub_request)
            else if(current_time >= stage_iter->finish_time){
                stage_iter->status = FINISH;
                remove_from_list(stage_iter, &(stage_iter->task->running_stage_head));
                //释放资源
                stage_iter->acc_unit->current_state = READY;
                stage_iter->acc_unit->next_state = RUNNING;
                stage_iter->acc_unit->next_state_predict_time = 0x7fffffffffffffffll; //从pagemap.h考来的最大值
                stage_iter->acc_unit = NULL;

                if(current_time > stage_iter->task->finish_time) //设置这个task的最晚完成的stage的时间，用于输出信息
                    stage_iter->task->finish_time = current_time;

                stage_iter->task->total_finished_stage++;
                //遍历所有子任务，增加其完成的父任务
                struct stage_dep* child_stage_iter = stage_iter->child_stage_head;
                while(child_stage_iter!=NULL){
                    child_stage_iter->stage->finished_parent_stage++;
                    if(child_stage_iter->stage->finished_parent_stage >= child_stage_iter->stage->total_parent_stage){ //如果所有父stage都完成了
                        if(child_stage_iter->stage->dispatched == 0){
                            insert_to_list(child_stage_iter->stage, &(child_stage_iter->stage->task->ready_stage_head));
                            child_stage_iter->stage->status = READY;
                            child_stage_iter->stage->dispatched = 1;
                        }
                    }
                    child_stage_iter = child_stage_iter->next;
                }
            }

            stage_iter = next_iter;
        }
        //步骤2.将ready list中的任务按照CPD插入各个单元的请求队列
        stage_iter = task_iter->ready_stage_head;
        while(stage_iter!=NULL){
            next_iter = stage_iter->next_stage_of_status;

            //将任务从ready队列中取出来
            remove_from_list(stage_iter, &(stage_iter->task->ready_stage_head));

            //插入到各个单元所属的队列中
            if(stage_iter->ope <= 1){
                push_stage(stage_iter, &(scheduler->chip_stage_list_head[stage_iter->channel*scheduler->ssd->parameter->chip_channel[0] + stage_iter->chip]));
            }
            else if(stage_iter->ope == RECSSD){
                push_stage(stage_iter, &(scheduler->recssd_stage_list_head));
            }
            else if(stage_iter->ope == IMAGE){
                push_stage(stage_iter, &(scheduler->image_stage_list_head));
            }
            else if(stage_iter->ope == TEXT){
                push_stage(stage_iter, &(scheduler->text_stage_list_head));
            }

            stage_iter = next_iter;
        }

        task_iter = task_iter->next_task;
    }

    //步骤3.从头遍历每个请求单元队列，pop已完成的stage(步骤1设置的)，然后按序分发任务
    struct stage* stage_in_list = NULL;
    struct stage* pre_stage_in_list = NULL; //用于删除节点
    struct stage* next_stage_in_list = NULL; //用于遍历节点
    for(int i=0; i < scheduler->ssd->parameter->chip_channel[0] * scheduler->ssd->parameter->channel_number; i++){
        //处理每个chip上的io请求
        stage_in_list = scheduler->chip_stage_list_head[i];
        next_stage_in_list = NULL; //用于遍历节点
        while(stage_in_list != NULL){
            next_stage_in_list = stage_in_list->next_stage_of_unit;

            if(stage_in_list->status == FINISH){
                //当前任务完成了，应该从队列中删除。只可能是第一个节点，因为如果第一个是RUNNING就退出了，如果是READY就分配且退出
                scheduler->chip_stage_list_head[i] = stage_in_list->next_stage_of_unit;
                stage_in_list->next_stage_of_unit = NULL;
                //不用移动pre stage,因为删除了当前节点后pre stage是没有变的
            }

            else if(stage_in_list->status == RUNNING){ //如果当前任务没有完成，直接退出即可
                break;
            }

            else if(stage_in_list->status == READY){ //能运行到这里说明现在单元空闲，因为不空闲的话说明有RUNNING的就会已经退出了
                insert_to_list(stage_in_list, &stage_in_list->task->running_stage_head);
                stage_in_list->status = RUNNING;
                //以下代码来自allocate_location
                struct channel_info * p_ch = &(scheduler->ssd->channel_head[stage_in_list->channel]);
                struct sub_request* sub = stage_in_list->sub_request;
                if(stage_in_list->ope == READ){ //挂到相应的channel上
                    if (p_ch->subs_r_tail!=NULL)
                    {
                        p_ch->subs_r_tail->next_node=sub;
                        p_ch->subs_r_tail=sub;
                    } 
                    else
                    {
                        p_ch->subs_r_head=sub;
                        p_ch->subs_r_tail=sub;
                    }
                }
                else if(stage_in_list->ope == WRITE){
                    if (p_ch->subs_w_tail!=NULL)
                    {
                        p_ch->subs_w_tail->next_node=sub;
                        p_ch->subs_w_tail=sub;
                    } 
                    else
                    {
                        p_ch->subs_w_tail=sub;
                        p_ch->subs_w_head=sub;
                    }
                }

                break;
            }
            else{
                printf("impossible!!!!!!!!!!!!");
                getchar();
            }

            //如果单元还没被跑满就继续找下一个
            stage_in_list = next_stage_in_list;
        }
    }

    //从头处理ndp请求
    stage_in_list = scheduler->recssd_stage_list_head;
    pre_stage_in_list = NULL; //用于删除节点
    next_stage_in_list = NULL; //用于遍历节点
    int running_stage = 0; //当前正在运行的stage数量
    while(stage_in_list != NULL){
        next_stage_in_list = stage_in_list->next_stage_of_unit;

        if(stage_in_list->status == FINISH){
            //当前任务完成了，应该从队列中删除
            if(pre_stage_in_list == NULL){ //说明是头节点
                scheduler->recssd_stage_list_head = stage_in_list->next_stage_of_unit;
            }
            else{ //如果不是头节点
                pre_stage_in_list->next_stage_of_unit = stage_in_list->next_stage_of_unit;
            }
            stage_in_list->next_stage_of_unit = NULL;
            //不用移动pre stage,因为删除了当前节点后pre stage是没有变的
        }

        else if(stage_in_list->status == RUNNING){ //如果当前任务没有完成
            running_stage++; 
            pre_stage_in_list = stage_in_list;
        }

        else if(stage_in_list->status == READY){
            if(running_stage < scheduler->ssd->parameter->recssd_count){ //如果单元还有空余的
                //分发到一个单元中
                for(int i=0; i<scheduler->ssd->parameter->recssd_count; i++){
                    if(scheduler->ssd->recssd_unit_head[i].current_state == READY){
                        //设置加速单元的属性
                        scheduler->ssd->recssd_unit_head[i].current_state = RUNNING;
                        scheduler->ssd->recssd_unit_head[i].next_state = READY;
                        scheduler->ssd->recssd_unit_head[i].next_state_predict_time = scheduler->ssd->current_time + scheduler->ssd->parameter->recssd_time;

                        stage_in_list->start_time = scheduler->ssd->current_time;
                        stage_in_list->finish_time = scheduler->ssd->current_time + scheduler->ssd->parameter->recssd_time;
                        stage_in_list->acc_unit = &(scheduler->ssd->recssd_unit_head[i]);
                        stage_in_list->dispatched = 1;

                        insert_to_list(stage_in_list, &stage_in_list->task->running_stage_head);

                        stage_in_list->status = RUNNING;
                        running_stage++;

                        break; //分配到单元了退出即可
                    }
                }
                if(stage_in_list->status != RUNNING){
                    printf("[dispatch CPCU]impossible!!!%d\n",stage_in_list->id);
                    getchar();
                }
            }
            pre_stage_in_list = stage_in_list;
        }
        
        if(running_stage >= scheduler->ssd->parameter->recssd_count){
            break; //如果所有单元都跑起来了就可以退出了
        }

        //如果单元还没被跑满就继续找下一个
        stage_in_list = next_stage_in_list;
    }

    //图像检索
    stage_in_list = scheduler->image_stage_list_head;
    pre_stage_in_list = NULL; //用于删除节点
    next_stage_in_list = NULL; //用于遍历节点
    running_stage = 0; //当前正在运行的stage数量
    while(stage_in_list != NULL){
        next_stage_in_list = stage_in_list->next_stage_of_unit;

        if(stage_in_list->status == FINISH){
            //当前任务完成了，应该从队列中删除
            if(pre_stage_in_list == NULL){ //说明是头节点
                scheduler->image_stage_list_head = stage_in_list->next_stage_of_unit;
            }
            else{ //如果不是头节点
                pre_stage_in_list->next_stage_of_unit = stage_in_list->next_stage_of_unit;
            }
            stage_in_list->next_stage_of_unit = NULL;
            //不用移动pre stage,因为删除了当前节点后pre stage是没有变的
        }

        else if(stage_in_list->status == RUNNING){ //如果当前任务没有完成
            running_stage++; 
            pre_stage_in_list = stage_in_list;
        }

        else if(stage_in_list->status == READY){
            if(running_stage < scheduler->ssd->parameter->image_count){ //如果单元还有空余的
                //分发到一个单元中
                for(int i=0; i<scheduler->ssd->parameter->image_count; i++){
                    if(scheduler->ssd->image_unit_head[i].current_state == READY){
                        //设置加速单元的属性
                        scheduler->ssd->image_unit_head[i].current_state = RUNNING;
                        scheduler->ssd->image_unit_head[i].next_state = READY;
                        scheduler->ssd->image_unit_head[i].next_state_predict_time = scheduler->ssd->current_time + scheduler->ssd->parameter->image_time;

                        stage_in_list->start_time = scheduler->ssd->current_time;
                        stage_in_list->finish_time = scheduler->ssd->current_time + scheduler->ssd->parameter->image_time;
                        stage_in_list->acc_unit = &(scheduler->ssd->image_unit_head[i]);
                        stage_in_list->dispatched = 1;

                        insert_to_list(stage_in_list, &stage_in_list->task->running_stage_head);

                        stage_in_list->status = RUNNING;
                        running_stage++;

                        break; //分配到单元了退出即可
                    }
                }
                if(stage_in_list->status != RUNNING){
                    printf("[dispatch CPCU]impossible!!!%d\n",stage_in_list->id);
                    getchar();
                }
            }
            pre_stage_in_list = stage_in_list;
        }
        
        if(running_stage >= scheduler->ssd->parameter->image_count){
            break; //如果所有单元都跑起来了就可以退出了
        }

        //如果单元还没被跑满就继续找下一个
        stage_in_list = next_stage_in_list;
    }

    //文本检索
    stage_in_list = scheduler->text_stage_list_head;
    pre_stage_in_list = NULL; //用于删除节点
    next_stage_in_list = NULL; //用于遍历节点
    running_stage = 0; //当前正在运行的stage数量
    while(stage_in_list != NULL){
        next_stage_in_list = stage_in_list->next_stage_of_unit;

        if(stage_in_list->status == FINISH){
            //当前任务完成了，应该从队列中删除
            if(pre_stage_in_list == NULL){ //说明是头节点
                scheduler->text_stage_list_head = stage_in_list->next_stage_of_unit;
            }
            else{ //如果不是头节点
                pre_stage_in_list->next_stage_of_unit = stage_in_list->next_stage_of_unit;
            }
            stage_in_list->next_stage_of_unit = NULL;
            //不用移动pre stage,因为删除了当前节点后pre stage是没有变的
        }

        else if(stage_in_list->status == RUNNING){ //如果当前任务没有完成
            running_stage++; 
            pre_stage_in_list = stage_in_list;
        }

        else if(stage_in_list->status == READY){
            if(running_stage < scheduler->ssd->parameter->text_count){ //如果单元还有空余的
                //分发到一个单元中
                for(int i=0; i<scheduler->ssd->parameter->text_count; i++){
                    if(scheduler->ssd->text_unit_head[i].current_state == READY){
                        //设置加速单元的属性
                        scheduler->ssd->text_unit_head[i].current_state = RUNNING;
                        scheduler->ssd->text_unit_head[i].next_state = READY;
                        scheduler->ssd->text_unit_head[i].next_state_predict_time = scheduler->ssd->current_time + scheduler->ssd->parameter->text_time;

                        stage_in_list->start_time = scheduler->ssd->current_time;
                        stage_in_list->finish_time = scheduler->ssd->current_time + scheduler->ssd->parameter->text_time;
                        stage_in_list->acc_unit = &(scheduler->ssd->text_unit_head[i]);
                        stage_in_list->dispatched = 1;

                        insert_to_list(stage_in_list, &stage_in_list->task->running_stage_head);

                        stage_in_list->status = RUNNING;
                        running_stage++;

                        break; //分配到单元了退出即可
                    }
                }
                if(stage_in_list->status != RUNNING){
                    printf("[dispatch CPCU]impossible!!!%d\n",stage_in_list->id);
                    getchar();
                }
            }
            pre_stage_in_list = stage_in_list;
        }
        
        if(running_stage >= scheduler->ssd->parameter->text_count){
            break; //如果所有单元都跑起来了就可以退出了
        }

        //如果单元还没被跑满就继续找下一个
        stage_in_list = next_stage_in_list;
    }

}

//调度核心函数
int dispatch(struct scheduler* scheduler){
    //printf("system time:%u\n",scheduler->ssd->current_time);
    //现在所有的请求都在scheduler的task链表中并且没有分发
    struct task* task_iter = scheduler->task_head;
    while(task_iter != NULL){
        //把所有task目前可执行的stage都打印出来看看
        //print_task_status(task_iter);

        //测试算法，遍历所有scheduler把没有分配到相应单元的请求全部分发下去
        //1.检查已完成队列，如果队列中有预计时间完成时间小于等于系统时间的则标记为完成。将其移除并将子任务的已完成父任务++，如果子任务的所有父任务都完成了则将其提到ready队列中。
        struct stage* stage_iter = task_iter->running_stage_head;
        struct stage* next_iter = NULL;
        unsigned long current_time = scheduler->ssd->current_time;
        while(stage_iter!=NULL){
            next_iter = stage_iter->next_stage_of_status; //因为可能会从其所在状态链表中remove，所以要提前把后一个节点保存下来

            //或者sub_request已完成(这部分由process()函数处理不好修改，我们去查询其是否完成即可)
            if(stage_iter->sub_request != NULL){ //与某个io子请求绑定了的，说明是个io请求
                if((stage_iter->sub_request->current_state == SR_COMPLETE)||((stage_iter->sub_request->next_state==SR_COMPLETE)&&(stage_iter->sub_request->next_state_predict_time<=current_time))){
                    //printf("remove stage %d of task %d from running list\n",stage_iter->id, stage_iter->task->task_id);
                    remove_from_list(stage_iter, &(stage_iter->task->running_stage_head));
                    if(current_time > stage_iter->task->finish_time) //设置这个task的最晚完成的stage的时间，用于输出信息
                        stage_iter->task->finish_time = current_time;

                    stage_iter->task->total_finished_stage++;
                    //遍历所有子任务，增加其完成的父任务
                    struct stage_dep* child_stage_iter = stage_iter->child_stage_head;
                    while(child_stage_iter!=NULL){
                        child_stage_iter->stage->finished_parent_stage++;
                        if(child_stage_iter->stage->finished_parent_stage >= child_stage_iter->stage->total_parent_stage){ //如果所有父stage都完成了
                            if(child_stage_iter->stage->dispatched == 0){
                                insert_to_list(child_stage_iter->stage, &(child_stage_iter->stage->task->ready_stage_head));
                                child_stage_iter->stage->dispatched = 1;
                            }
                        }
                        child_stage_iter = child_stage_iter->next;
                    }
                }
            }
            //如果系统时间超过了stage完成时间(用于判断ndp步骤是否完成，因为ndp步骤没有对应的sub_request)
            else if(current_time >= stage_iter->finish_time){
                remove_from_list(stage_iter, &(stage_iter->task->running_stage_head));
                //释放资源
                stage_iter->acc_unit->current_state = READY;
                stage_iter->acc_unit->next_state = RUNNING;
                stage_iter->acc_unit->next_state_predict_time = 0x7fffffffffffffffll; //从pagemap.h考来的最大值
                stage_iter->acc_unit = NULL;

                if(current_time > stage_iter->task->finish_time) //设置这个task的最晚完成的stage的时间，用于输出信息
                    stage_iter->task->finish_time = current_time;

                stage_iter->task->total_finished_stage++;
                //遍历所有子任务，增加其完成的父任务
                struct stage_dep* child_stage_iter = stage_iter->child_stage_head;
                while(child_stage_iter!=NULL){
                    child_stage_iter->stage->finished_parent_stage++;
                    if(child_stage_iter->stage->finished_parent_stage >= child_stage_iter->stage->total_parent_stage){ //如果所有父stage都完成了
                        if(child_stage_iter->stage->dispatched == 0){
                            insert_to_list(child_stage_iter->stage, &(child_stage_iter->stage->task->ready_stage_head));
                            child_stage_iter->stage->dispatched = 1;
                        }
                    }
                    child_stage_iter = child_stage_iter->next;
                }
            }

            stage_iter = next_iter;
        }
        //2.将ready_stage_head中的任务分发到各个队列中
        stage_iter = task_iter->ready_stage_head;
        while(stage_iter!=NULL){
            next_iter = stage_iter->next_stage_of_status;
            
            //printf("push stage %d of task %d to running list\n",stage_iter->id, stage_iter->task->task_id);
            if(stage_iter->ope == READ){ //如果是io任务就挂到相应的channel上
                remove_from_list(stage_iter, &stage_iter->task->ready_stage_head);
                insert_to_list(stage_iter, &stage_iter->task->running_stage_head);
                //以下代码来自create_sub_request
                struct channel_info * p_ch = &(scheduler->ssd->channel_head[stage_iter->channel]);
                struct sub_request* sub = stage_iter->sub_request;
                if (p_ch->subs_r_tail!=NULL)
                {
                    p_ch->subs_r_tail->next_node=sub;
                    p_ch->subs_r_tail=sub;
                } 
                else
                {
                    p_ch->subs_r_head=sub;
                    p_ch->subs_r_tail=sub;
                }
            }
            else if(stage_iter->ope == WRITE){ //如果是ndp任务就挂到当前空闲的ip核上。如果ip核没有空闲的则该任务不能执行
                remove_from_list(stage_iter, &stage_iter->task->ready_stage_head);
                insert_to_list(stage_iter, &stage_iter->task->running_stage_head);
                //以下代码来自allocate_location
                struct channel_info * p_ch = &(scheduler->ssd->channel_head[stage_iter->channel]);
                struct sub_request* sub = stage_iter->sub_request;

                if (p_ch->subs_w_tail!=NULL)
                {
                    p_ch->subs_w_tail->next_node=sub;
                    p_ch->subs_w_tail=sub;
                } 
                else
                {
                    p_ch->subs_w_tail=sub;
                    p_ch->subs_w_head=sub;
                }
            }
            else if(stage_iter->ope == RECSSD){
                //检查是否相应加速器有空闲的
                for(int i=0; i<scheduler->ssd->parameter->recssd_count; i++){
                    if(scheduler->ssd->recssd_unit_head[i].current_state == READY){
                        //设置加速单元的属性
                        scheduler->ssd->recssd_unit_head[i].current_state = RUNNING;
                        scheduler->ssd->recssd_unit_head[i].next_state = READY;
                        scheduler->ssd->recssd_unit_head[i].next_state_predict_time = current_time + scheduler->ssd->parameter->recssd_time;

                        stage_iter->start_time = current_time;
                        stage_iter->finish_time = current_time + scheduler->ssd->parameter->recssd_time;
                        stage_iter->acc_unit = &(scheduler->ssd->recssd_unit_head[i]);
                        stage_iter->dispatched = 1;

                        remove_from_list(stage_iter, &stage_iter->task->ready_stage_head);
                        insert_to_list(stage_iter, &stage_iter->task->running_stage_head);

                        break; //分配到单元了退出即可
                    }
                }
                //如果没有分配到相应单元则不进行操作
            }
            else if(stage_iter->ope == IMAGE){
                for(int i=0; i<scheduler->ssd->parameter->image_count; i++){
                    if(scheduler->ssd->image_unit_head[i].current_state == READY){
                        //设置加速单元的属性
                        scheduler->ssd->image_unit_head[i].current_state = RUNNING;
                        scheduler->ssd->image_unit_head[i].next_state = READY;
                        scheduler->ssd->image_unit_head[i].next_state_predict_time = current_time + scheduler->ssd->parameter->image_time;

                        stage_iter->start_time = current_time;
                        stage_iter->finish_time = current_time + scheduler->ssd->parameter->image_time;
                        stage_iter->acc_unit = &(scheduler->ssd->image_unit_head[i]);
                        stage_iter->dispatched = 1;

                        remove_from_list(stage_iter, &stage_iter->task->ready_stage_head);
                        insert_to_list(stage_iter, &stage_iter->task->running_stage_head);

                        break; //分配到单元了退出即可
                    }
                }
            }
            else if(stage_iter->ope == TEXT){
                for(int i=0; i<scheduler->ssd->parameter->text_count; i++){
                    if(scheduler->ssd->text_unit_head[i].current_state == READY){
                        //设置加速单元的属性
                        scheduler->ssd->text_unit_head[i].current_state = RUNNING;
                        scheduler->ssd->text_unit_head[i].next_state = READY;
                        scheduler->ssd->text_unit_head[i].next_state_predict_time = current_time + scheduler->ssd->parameter->text_time;

                        stage_iter->start_time = current_time;
                        stage_iter->finish_time = current_time + scheduler->ssd->parameter->text_time;
                        stage_iter->acc_unit = &(scheduler->ssd->text_unit_head[i]);
                        stage_iter->dispatched = 1;

                        remove_from_list(stage_iter, &stage_iter->task->ready_stage_head);
                        insert_to_list(stage_iter, &stage_iter->task->running_stage_head);

                        break; //分配到单元了退出即可
                    }
                }
            }

            stage_iter = next_iter;
        }

        task_iter = task_iter->next_task;
    }

    return 0;
}

void init_scheduler(struct ssd_info* ssd){
    struct scheduler* tmp_scheduler = (struct scheduler*)malloc(sizeof(struct scheduler));
    alloc_assert(tmp_scheduler,"ssd->scheduler");

    ssd->scheduler = tmp_scheduler;
    tmp_scheduler->ssd = ssd;
    tmp_scheduler->task_head=NULL;
    tmp_scheduler->task_tail=NULL;
    tmp_scheduler->task_count=0; //一开始有0个任务
    tmp_scheduler->total_task_count=1; //从1开始，与trace的行相对应

    //初始化各个单元的数组
    tmp_scheduler->chip_stage_list_head = (struct stage**)malloc(ssd->parameter->channel_number*ssd->parameter->chip_channel[0]*sizeof(struct stage*));
    tmp_scheduler->recssd_stage_list_head = NULL;
    tmp_scheduler->text_stage_list_head = NULL;
    tmp_scheduler->image_stage_list_head = NULL;

    //每个指针设置为NULL
    memset(tmp_scheduler->chip_stage_list_head, NULL, ssd->parameter->channel_number*ssd->parameter->chip_channel[0]*sizeof(struct stage*));
}

struct stage* init_stage(){ //初始化阶段，新建的stage只需要更改需要的部分即可
    struct stage* stage = (struct stage*)malloc(sizeof(struct stage));

    stage->id = 0;
    stage->ope = 0;
    stage->lpn = 0;
    stage->channel = 0;
    stage->chip = 0;
    stage->dispatched = 0; //是否已经分发给各个功能单元，0表示未分发，1表示已分发(好像和status重复了?...)
    stage->status = READY; //状态，0等待，1正在运行，2完成
    stage->task = NULL; //记录所属的任务，用于完成阶段后的标记
    stage->CPD = -1; //关键度为-1表示尚未初始化

    stage->start_time = 0;
    stage->finish_time = 0;
    
    stage->predict_time = 0;

    stage->total_parent_stage = 0;
    stage->finished_parent_stage = 0;

    stage->child_stage_head = NULL; 
    stage->parent_stage_head = NULL;

    stage->next_stage_of_unit = NULL; //指向同一单元请求队列的下一个任务，用于功能单元执行任务。主要是给CPCU使用
    stage->prev_stage_of_unit = NULL;

    stage->next_stage_of_task = NULL;

    stage->next_stage_of_status = NULL;
    stage->prev_stage_of_status = NULL;

    stage->acc_unit = NULL;

    stage->sub_request = NULL; //与ssdsim的sub_request相连接，便于修改状态及分发任务
}

struct stage* get_stage(int stage_id, struct task* task){
    struct stage* iter = task->stage_queue_head;

    while(iter!=NULL){
        if(iter->id == stage_id){
            break;
        }
        iter = iter->next_stage_of_task;
    }

    return iter;
}

void print_task(struct task* task, char* prefix){
    if(prefix!=NULL)
        printf("%s ",prefix);
    printf("id:%u ",task->task_id);

    struct stage* iter = task->stage_queue_head;
    printf("op:%d ",task->task_ope);
    while(iter!=NULL){
        printf("%d:%d:%d:%d--",iter->id,iter->ope,iter->lpn,iter->status);
        iter = iter->next_stage_of_task;
    }
    printf("\n");

    //打印每个阶段的依赖
    struct stage_dep* stage_dep_iter;
    iter = task->stage_queue_head;
    while(iter!=NULL){
        printf("  stage %d parent:",iter->id);
        stage_dep_iter = iter->parent_stage_head;
        while(stage_dep_iter!=NULL){
            printf("%d ",stage_dep_iter->id);
            stage_dep_iter = stage_dep_iter->next;
        }

        printf(" child:");
        stage_dep_iter = iter->child_stage_head;
        while(stage_dep_iter!=NULL){
            printf("%d ",stage_dep_iter->id);
            stage_dep_iter = stage_dep_iter->next;
        }
        
        printf("\n");
        iter = iter->next_stage_of_task;
    }
    printf("\n");
}

//递归地删除该请求的所有的子请求
void delete_stage(struct stage* stage){  
    //printf("delete stage %d ope:%d\n",stage->id,stage->ope);   

    struct stage_dep* iter1 = stage->child_stage_head;
    struct stage_dep* iter2;
    while(iter1!=NULL){
        iter2 = iter1->next;
        free(iter1);
        iter1 = iter2;
    }

    iter1 = stage->parent_stage_head;
    while(iter1!=NULL){
        iter2 = iter1->next;
        free(iter1);
        iter1 = iter2;
    }

    free(stage);
}

void delete_task(struct task* task){
    //printf("delete task %5d\n",task->task_id);
    if(task!=NULL){
        //删除所有的stage
        struct stage* iter = task->stage_queue_head;
        struct stage* after = NULL;
        while(iter!=NULL){
            after = iter->next_stage_of_task;
            delete_stage(iter);
            iter = after;
        }        

        free(task);
        //scheduler减一的任务由调用者负责，就不用传个ssd_info进来了
    }
    else{
        printf("delete task %5d error!\n",task->task_id);
    }
}